//最长的斐波那契子序列的长度 二维子序列dp
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) 
    {
        //如果单单以nums[i] 定义dp数组 我们无从知道这个斐波那契数列是什么
        //但只要有两个值作为参考 就可以将整个斐波那契数列找出来 所以需要二维dp
        //dp[i][j] 以arr[i] 和 arr[j]结尾的最长的斐波那契子序列的长度
        int n=arr.size();
        int res=0;
        vector<vector<int>>dp(n,vector<int>(n,2));
        unordered_map<int,int>hash;
        for(int i=0;i<n;i++) hash[arr[i]]=i;
        for(int j=2;j<n;j++)
        {
            for(int i=1;i<j;i++)
            {
                auto it=hash.find(arr[j]-arr[i]);
                if(it!=hash.end() && it->second < i)
                {
                    int index=it->second;
                    dp[i][j]=dp[index][i]+1;
                    res=res<dp[i][j]?dp[i][j]:res;
                }
            }
        }
        return res;
    }
};
